1. Field of the Invention
This invention pertains to a method for characterizing networks. More particularly, the invention pertains to a cut set-based method for performing risk and reliability analysis of arbitrarily interconnected networks wherein all-terminal reliability is a factor to be considered in the networks' design and maintenance. The method applies equally well to planar and non-planar networks.
2. Description of the Related Art
During recent years there has been a dramatic increase in the use and importance of networks, generally, and of information and communications systems, specifically, in broad aspects of life. Today it is not unusual for the failure of these systems to result in huge financial losses, and even to threaten property, cause environmental burdens, and endanger of human life. Businesses count on reliable telecommunications systems to transfer time-critical business information, to enable collaboration of employees at distant corporate locations, and to perform financial transactions. Individuals rely on these infrastructures not only for day-to-day communications, but also as a primary means of assuring their health and safety through immediate access to emergency services. Governments use telecommunications services to coordinate actions during times of natural disaster and national emergency. Clearly, the presence of a reliable telecommunications and information transport infrastructure is critical to many aspects of our country's well being.
The networks just described are more and more becoming characterized by nonhierarchical architectures that are arbitrarily interconnected such as the U.S. public switched telephone network presently in use and large-scale asynchronous mode data communications networks which are currently undergoing development. Probabilistic risk and reliability analysis (PRA) methods have been used to assess the reliability of complex electromechanical systems ranging from individual components within automobiles to large precision machine tools, complex semiconductor fabrication facilities, nuclear power reactors, chemical processing plants, aircraft and spacecraft. The reason that PRA methods have not been widely applied to analyze communications networks and other arbitrarily interconnected networks is that the traditional PRA modeling techniques, such as reliability block diagrams, fault trees and event trees result in vast mathematical inefficiencies when applied to such networks. In addition, the derivation of models using these techniques is logically difficult and error-prone for such networks. Traditional techniques for network analysis are designed to examine the root causes and consequences of a single, well-defined failure condition, and can become extraordinarily complex when applied to an all-terminal reliability problem (i.e., "Can everybody on this network talk to everybody else?" ). There can, in fact, be a combinatorial explosion in model complexity as one considers the conditions that can cause loss of connectivity between every possible pair of points in the network. The combinatorial expansion problem causes the use of PRA techniques to become intractable for modeling all but the most rudimentary networks.
Prior attempts to perform reliability analyses for communications and other similar networks have focused on path set theory rather than cut set theory. Briefly stated, path set theory seeks to identify all of the possible paths by which information can pass between two selected points within a network, while cut set theory seeks to identify all of the possible combinations of failures that can prevent information from passing through the network. Path sets have, until now, been the method of choice for network reliability analysis for two main reasons: First, a number of efficient pathing algorithms exist in the literature, and second, the same network will often produce far fewer path sets than cut sets. Thus, it has historically been convenient and efficient to examine network reliability with path sets.
While path sets have historically been easier to generate than cut sets, they are a less useful than cut sets for the purposes of reliability analysis. Importance measures derived from cut sets can provide network design and operations personnel with key information about which network elements are the most important to system reliability and where to direct investment to obtain the most cost-effective network improvement. Unfortunately, these importance measures cannot be derived directly from path sets. This is why a robust network assessment method that is based on cut sets rather than path sets is sought.